package com.example.lcode.backtrack;

import java.util.Arrays;

public class Question473 {

    public boolean makesquare(int[] matchsticks) {
        int sum  = Arrays.stream(matchsticks).sum();
        if (sum % 4 != 0) {
            return false;
        }
        int avg = sum / 4;
        boolean []sign = new boolean[matchsticks.length];
        Arrays.sort(matchsticks);
        int calc = 0;
        int count = 0;
        return makesquare(matchsticks, calc, count, avg, sign, matchsticks.length - 1);
    }

    private boolean makesquare(int[] matchsticks, int calc, int count, int avg, boolean[] sign, int beginIndex) {
        if (avg == calc) {
            beginIndex = matchsticks.length - 1;
            calc = 0;
            count++;
        }
        if (count == 4) {
            return true;
        }
        boolean makeItOk = false;
        for (int i = beginIndex; i  >= 0 ; i--) {
            if (!sign[i]) {
                if (calc + matchsticks[i] <= avg) {
                    sign[i] = true;
                    makeItOk =  makesquare(matchsticks, calc + matchsticks[i], count, avg, sign, i - 1);
                    sign[i] = false;
                }
            }
            if (makeItOk) {
                break;
            }
        }
        return makeItOk;
    }


    public static void main(String[] args) {
        Question473 question473 = new Question473();
        boolean makesquare = question473.makesquare(new int[]{5,5,5,5,4,4,4,4,3,3,3,3});
        System.out.println(makesquare);
    }

}
